In the prior art, data communications networks have allowed communciation between user terminals, computers, and other peripheral equipment. As computer capability increase, a single computer is made to serve many users; and as computer cost decreases, computers are increasingly widely dispersed to serve the individual users. While computer costs have been falling rapidly most peripheral equipment costs have been falling more slowly. One way to minimize the expense of this equipment is to share it. Consequently, a need for more efficient ways to share the relatively expensive peripheral equipment increases. And as more and more inexpensive computers proliferate and are dispersed, the information flowing to and from these computers also becomes more widely dispersed. As a result, a parallel need to access information remotely located increases. The net result is a corresponding increase in numbers and complexity of data communications networks.
In these communications networks, data are handled either by centralized control or distributed control. The simpler of the two approaches in handling data is by centralized control. However, because a single controller dictates the flow of data in the network, it can become a bottleneck if it has an inadequate capacity to handle all the data. Worse yet, it can cause the entire data communications network to fail if it itself fails. For these reasons, network control is often distributed to the remote information points, or nodes.
In general, two generic distributed control tecniques are used. One is generally referred to as a circuit switching technique, while the other technique is generally referred to as a packet switching technique. Circuit switching techniques can be analogized to telephone network switching, which for short and bursty communications typical in computer applications requires a high overhead in terms of capacity. For short bursts of communications, the time required to establish the connection can be very large relative to the time of actual transmission. However, if the connection is maintained for a longer period of time it is unused and wasted during the large fraction of idle time between bursts. On the other hand, packet switching can be analogized to letter handling by the postal system, except that the letters are computer data packets sorted and transmitted very quickly by increasingly inexpensive electronics. Short communications can be carried efficiently in a single data packet, and longer communications can be handled with a series of packets, none of which occupy communications resources during the frequent idle periods between bursts.
Accordingly, there exists a present requirement for a packet switching communications system which is efficient and reliable while requiring minimum hardware. An additional requirement to the communications system is a capacity of effecting communications between various computers and peripherals with a high probability of delivering the packet without the aid of central control. There is a further requirement to provide a communications network which is simple to produce, requires simple parts in its attachments and is generally of low complexity. One communications system proposed in the prior art to meet these requirements is disclosed in "Multipoint Data Communications System with Collision Detection," U.S. Pat. No. 4,063,220, by Metcalfe et al., herein incorporated by reference in full. The present invention provides an alternate communications system to meet these requirements.
In general, information is carried on such systems in units usually called packets. In the ensuing discussions, packets will be used to describe data which flow inseparably through a network; they may contain whole messages or fragments thereof.
In accordance with the invention the protocols control communications by viewing packets as contending for a limited resource, namely, the outbound data link to a remote node of the communications network. Contention among the packets at a node which are to use a link is resolved by assigning priorites to these contending packets. At a particular node, packets which are generated at the local computer or other local device are called "local" packets. In contrast are "network" packets: network packets are those packets generated at nodes within the network other than the local one. All local and all network packets are treated in a first-in-first-out priority order; and all network packets are given priority over all local packets.
Priority between local and network packets takes one of three forms: simple priority, preemptive priority with repeat, and preemptive priority with resume. Simple priority, or priority with no preemption, indicates that the priority rule is invoked at the end of the service by the limited resource or when no service is underway. The priority rule can be stated succinctly: once service has commenced on a job the service is always completed. Preemptive resume priority indicates that the priority rule is always in effect. The arrival of a high priority job immediately terminates a lower priority one. However, after the preempting higher priority job has been serviced the lower priority job is again serviced. The service resumes where it had stopped last time. No service is lost. Preemptive repeat priority similarly indicates that the priority rule is always in effect. However, when the partially serviced lower priority job is again serviced, all the service previously performed is lost and the job has to start again. The preferred embodiment of the invention incorporates the first two implementations of the priority rule, viz., simple priority and preemptive priority with resume.
The simple alternate communications system in accordance with the preferred embodiment of the invention defines a protocol for handling packets generated locally, viz., local packets, and those arriving at the node from the network, viz., network packets. With this protocol, network packets pass through all intervening nodes except (1) the node where they originate, viz., the source node of local node, to which they are local packets, and (2) their destination node, where they are usually removed from the network. These packets comprise through-traffic at the nodes between their source and destination.
In the through-trafic preemptive mode, a network packet entering and passing through the node takes priority over any local packet transmission in the node. The network packet entering a node is initially delayed by being routed to an input shift register. In the meanwhile, any transmission of a local packet is terminated, and a node output switch selects the output of the shift register through which the network packet is passed for transmission. Assuming receiver removal is used, if the network packet's destination is the node itself, the network packet would not be routed through and out of the node; rather the packet would be removed from the network.
By adding a delay circuit in the path of the network packet as it emerges from the input shift register, a nonpreemptive through-traffic mode can be implemented. The delay circuit functions as a holding circuit for the network packet; it delays or stores the packet or a fraction of the packet. Transmission of a local packet is first completed. Then the network packet passing through the node is allowed to proceed from the delay circuit and is transmitted into the outbound link. Again assuming receiver removal, if the network packet's destination is the node only, the network packet is not retransmitted into the network.
Several advantages in addition to simplicity are achieved with the present invention. One major advantage is that by using delay circuits such as shift registers, there is time for the transmission of the local packet to be terminated without destroying the validity of the transmitted data. In other words, preemptive repeat is not necessary. Another is that when receiver removal is used, this protocol permits the rest of the ring (typically half the ring) to carry additional traffic. This approximately doubles capacity over that of most other protocols.
Another advantage with the present invention is the ease with which the system can be expanded or extended topologically. In prior art communications networks, a protocol typically has some characteristic which limits the domain of nodes which can cooperate in communication. If the structure is a bus, the limiting characteristic may be the extend of broadcasting on the bus. If the structure is a token or slotted ring, then the limiting characteristic may be the group of nodes that actually appear on that ring. In each case, the limiting characteristic prevents a straightforward extension of a basic communications protocol to multiple structures. In the prior art, to couple multiple structures, i.e., rings or busses, usually requires complicated "bridge" functions. These bridge functions require extensive processing for each packet passing through the bridge. Because of this, such bridge functions impede and slow transmission and, sometimes, act as bottlenecks. The protocol systems in accordance with the preferred embodiment of the invention do not have this limitation of the prior art. By adding more address comparators to facilitate routing, multiple network output ports from a node can be implemented simply. By adding storage for queuing, multiple network input ports can be attached to a single node. Thus, a bridge function is realized with only a little increase in complexity, with no loss in speed, and with no change in protocol. This is possible with the preferred embodiment of the invention because the packet is entirely self contained and is independent of its surroundings. It requires no tokens or slots for permission to transmit.